﻿using System;
using System.Collections.Generic;
using Algoritmia.Utils;
using Lists = Algoritmia.DataStructures.Lists;

namespace Algoritmia.Problems.Searching
{
    public class BinarySearcher<T> : ISortedSearcher<T>
    {
        #region ISortedSearcher<T> Members

        public int IndexOf(Lists.IList<T> list, T elem, Comparison<T> comparison = null)
        {
            comparison = AlgoritmiaFactory.GetDefaultComparison(comparison);
            int first = 0, last = list.Count - 1;
            while ( first < last )
            {
                int pivot = (first + last)/2; 
                if (comparison(elem,list[pivot]) < 0 )
                {
                    last = pivot;
                }
                else if (comparison(elem,list[pivot]) > 0 )
                {
                    first = pivot+1;
                }
                else
                {
                    return pivot;
                }
            }
            return comparison(list[first], elem) == 0 ? first : -1;
        }

        #endregion
    }
}
